package uk.org.landeg.euler.problems;

import java.util.Map;
import java.util.TreeMap;

import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;
import uk.org.landeg.euler.problems.lib.NumbersLib;

public class Problem053 extends AbstractProblem {
	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem053());
		launcher.solve();
	}

	@Override
	public String getDescription() {
		return "How many, not necessarily distinct, values of  nCr, for 1  n  100, are greater than one-million";
	}

	@Override
	public Integer getProblemNumber() {
		return 53;
	}

	
	@Override
	public Object solve() {
		notes.add("nCr >= 10^6 then lg(n!) - lg(r!) - lg((n-r)!) >= 6");
		notes.add("Generating factorials " + System.currentTimeMillis());
		Map<Integer, Double> lookup = getLogFactorials();
		notes.add("Done " + System.currentTimeMillis());
		double sum = 0.0;
		int count = 0;
		for (int n = 1; n <= 100 ; n++) {
			for (int r = 1 ; r < n ; r++) {
				if (lookup.get(n) - lookup.get(r) - lookup.get(n-r) > 6) {
					count++;
				}
			}
		}
		
		return count;
	}

	private static Map<Integer, Double> getLogFactorials () {
		TreeMap<Integer, Double> logFactorials = new TreeMap<Integer, Double>();
		for (int n = 1; n <= 100 ; n++) {
			logFactorials.put(n, NumbersLib.logFactorial(n));
		}
		return logFactorials;
	}
}
